Celestin Apprentice 7/Apprentice-Release7.iso/Environments/Small Eiffel 0.4.8/lib_std/linked_collection.e

Text File | 1997-04-13 | 5.8 KB | 320 lines | [TEXT/ttxt]

-- Part of SmallEiffel -- Read DISCLAIMER file -- Copyright (C)
-- Dominique COLNET and Suzanne COLLIN -- [e-mail]
--
deferred class LINKED_COLLECTION[E]
   --
   -- Common root for LINK_LIST[E] and LINK2_LIST[E].
   --

inherit COLLECTION[E] redefine first, last end;

feature

   lower: INTEGER is 1;
     -- Lower index bound is frozen.

feature {LINKED_COLLECTION}

   first_link: LINK[E];
     -- Void when empty or gives access to the first element.

   last_link: like first_link;
     -- Void when empty or gives access to the last element.

   mem_idx: INTEGER; mem_lnk: like first_link;
     -- To speed up accessing, `mem_idx' and `mem_lnk' is the
     -- memory of the last access done. For example, after
     -- item(1), `mem_idx' is 1 and `mem_lnk' is `first_link'.
     -- When list is empty, `first_link' is Void as well as
     -- `mem_lnk' and `mem_idx' is 0;
     --
feature

   upper: INTEGER;
     -- Memorized upper index bound.

feature -- Creation and Modification :

   make is
      -- Make an empty list;
      deferred
      end;

feature

   first: like item is
      do
     Result := first_link.item;
      end;

   last: like item is
      do
     Result := last_link.item;
      end;

feature -- Implementation of deferred :

   item, infix "@" (index: INTEGER): E is
      do
     if index /= mem_idx then
        go_item(index);
     end;
     Result := mem_lnk.item;
      end;

   put(element: like item; index: INTEGER) is
      do
     if index /= mem_idx then
        go_item(index);
     end;
     mem_lnk.set_item(element);
      end;

   count: INTEGER is
      do
     Result := upper;
      end;

   set_all_with(v: like item) is
      do
     if first_link /= Void then
        first_link.set_all_with(v);
     end;
      end;

   copy(other: like Current) is
      do
     from_collection(other);
      end;

   is_equal(other: like Current): BOOLEAN is
      local
     lnk1, lnk2: like first_link;
      do
     if Current = other then
        Result := true;
     elseif upper = other.upper then
        from
           Result := true;
           lnk1 := first_link;
           lnk2 := other.first_link;
        until
           lnk1 = Void or not Result
        loop
           Result := equal_like(lnk1.item,lnk2.item);
           lnk1 := lnk1.next;
           lnk2 := lnk2.next;
        end;
     end;
      end;

   index_of(x: like item): INTEGER is
      do
     from
        Result := lower;
     until
        (Result > upper) or else equal_like(x,item(Result))
     loop
        Result := Result + 1;
     end;
      end;

   fast_index_of(x: like item): INTEGER is
      local
     u: like upper;
      do
     from
        Result := lower;
        u := upper;
     until
        (Result > u) or else x = item(Result)
     loop
        Result := Result + 1;
     end;
      end;

   clear is
      do
     if first_link /= Void then
        first_link.free;
        first_link := Void;
        mem_idx := 0;
        mem_lnk := Void;
        upper := 0;
        last_link := Void;
     end;
      ensure then
     upper = 0
      end;

   from_collection(model: COLLECTION[like item]) is
      local
     i, up: INTEGER;
     lnk: like first_link;
      do
     if first_link = Void then
        from
           i := model.lower;
           up := model.upper;
        until
           i > up
        loop
           add_last(model.item(i));
           i := i + 1;
        end;
     else
        from
           lnk := first_link;
           i := model.lower;
           up := model.upper;
        until
           i > up
        loop
           if lnk = Void then
          add_last(model.item(i));
           else
          lnk.set_item(model.item(i));
          lnk := lnk.next;
           end;
           i := i + 1;
        end;
        if lnk = first_link then
           check
          model.count = 0
           end;
           clear;
        elseif lnk /= Void then
           i := model.count;
           if mem_idx /= i then
          go_item(i);
           end;
           check
          lnk = mem_lnk.next
           end;
           mem_lnk.set_next(Void);
           upper := i;
           last_link := mem_lnk;
           lnk.free;
        end;
     end;
      end;

   slice(low, up: INTEGER): like Current is
      local
     lnk: like first_link;
     i: INTEGER;
      do
     from
        !!Result.make;
        if mem_idx /= low then
           go_item(low);
        end;
        lnk := mem_lnk;
        i := up - low + 1;
     until
        i = 0
     loop
        Result.add_last(lnk.item);
        lnk := lnk.next;
        i := i - 1;
     end;
      end;

   nb_occurrences(element: like item): INTEGER is
      local
     lnk: like first_link;
      do
     from
        lnk := first_link;
     until
        lnk = Void
     loop
        if equal_like(element,lnk.item) then
           Result := Result + 1;
        end;
        lnk := lnk.next;
     end;
      end;

   free is
      local
     mem: MEMORY;
      do
     clear;
     mem.free(Current.to_pointer);
      end;

   force(element: E; index: INTEGER) is
      local
     v: like element;
      do
     from
     until
        index <= upper
     loop
        add_last(v);
     end;
     put(element,index);
      end;

   all_cleared: BOOLEAN is
      local
     l: like first_link;
     d: like item;
      do
     from
        Result := true;
        l := first_link;
     until
        not Result or else l = Void
     loop
        Result := d = l.item;
        l := l.next;
     end;
      end;

   remove_last is
      local
     mem: MEMORY;
      do
     if upper = 1 then
        make;
     else
        if upper - 1 /= mem_idx then
           go_item(upper - 1);
        end;
        upper := upper - 1;
        mem.free(last_link.to_pointer);
        last_link := mem_lnk;
        last_link.set_next(Void);
     end;
      end;

feature {NONE}

   go_item(index: INTEGER) is
      require
     valid_index(index);
     mem_idx /= index;
           mem_idx > 0;
     mem_lnk /= Void
      deferred
      ensure
     mem_idx = index;
     mem_lnk /= Void
      end;

invariant

   empty_status:
      first_link = Void implies
         (last_link = Void and upper = 0 and mem_idx = 0
      and mem_lnk = Void);

   not_empty_status:
      first_link /= Void implies
         (last_link /= Void and upper > 0 and mem_idx > 0
      and mem_lnk /= Void);

end -- LINKED_COLLECTION[E]